<!DOCTYPE html>
<html lang="en-us">
  <head>

    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    
<meta charset="UTF-8">
<title>Preventing Combinatorial Explosions | Elasticsearch: The Definitive Guide [2.x] | Elastic</title>
<link rel="home" href="index.html" title="Elasticsearch: The Definitive Guide [2.x]">
<link rel="up" href="docvalues-and-fielddata.html" title="Doc Values and Fielddata">
<link rel="prev" href="preload-fielddata.html" title="Preloading Fielddata">
<link rel="next" href="_closing_thoughts.html" title="Closing Thoughts">
<meta name="DC.type" content="Learn/Docs/Legacy/Elasticsearch/Definitive Guide/2.x">
<meta name="DC.subject" content="Elasticsearch">
<meta name="DC.identifier" content="2.x">
<meta name="robots" content="noindex,nofollow">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <script src="https://cdn.optimizely.com/js/18132920325.js"></script>
    <link rel="apple-touch-icon" sizes="57x57" href="/apple-icon-57x57.png">
    <link rel="apple-touch-icon" sizes="60x60" href="/apple-icon-60x60.png">
    <link rel="apple-touch-icon" sizes="72x72" href="/apple-icon-72x72.png">
    <link rel="apple-touch-icon" sizes="76x76" href="/apple-icon-76x76.png">
    <link rel="apple-touch-icon" sizes="114x114" href="/apple-icon-114x114.png">
    <link rel="apple-touch-icon" sizes="120x120" href="/apple-icon-120x120.png">
    <link rel="apple-touch-icon" sizes="144x144" href="/apple-icon-144x144.png">
    <link rel="apple-touch-icon" sizes="152x152" href="/apple-icon-152x152.png">
    <link rel="apple-touch-icon" sizes="180x180" href="/apple-icon-180x180.png">
    <link rel="icon" type="image/png" href="/favicon-32x32.png" sizes="32x32">
    <link rel="icon" type="image/png" href="/android-chrome-192x192.png" sizes="192x192">
    <link rel="icon" type="image/png" href="/favicon-96x96.png" sizes="96x96">
    <link rel="icon" type="image/png" href="/favicon-16x16.png" sizes="16x16">
    <link rel="manifest" href="/manifest.json">
    <meta name="apple-mobile-web-app-title" content="Elastic">
    <meta name="application-name" content="Elastic">
    <meta name="msapplication-TileColor" content="#ffffff">
    <meta name="msapplication-TileImage" content="/mstile-144x144.png">
    <meta name="theme-color" content="#ffffff">
    <meta name="naver-site-verification" content="936882c1853b701b3cef3721758d80535413dbfd">
    <meta name="yandex-verification" content="d8a47e95d0972434">
    <meta name="localized" content="true">
    <meta name="st:robots" content="follow,index">
    <meta property="og:image" content="https://www.elastic.co/static/images/elastic-logo-200.png">
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">
    <link rel="icon" href="/favicon.ico" type="image/x-icon">
    <link rel="apple-touch-icon-precomposed" sizes="64x64" href="/favicon_64x64_16bit.png">
    <link rel="apple-touch-icon-precomposed" sizes="32x32" href="/favicon_32x32.png">
    <link rel="apple-touch-icon-precomposed" sizes="16x16" href="/favicon_16x16.png">
    <!-- Give IE8 a fighting chance -->
    <!--[if lt IE 9]>
    <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
    <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
    <![endif]-->
    <link rel="stylesheet" type="text/css" href="/guide/static/styles.css">
  </head>

  <!--© 2015-2021 Elasticsearch B.V. Copying, publishing and/or distributing without written permission is strictly prohibited.-->

  <body>
    <!-- Google Tag Manager -->
    <script>dataLayer = [];</script><noscript><iframe src="//www.googletagmanager.com/ns.html?id=GTM-58RLH5" height="0" width="0" style="display:none;visibility:hidden"></iframe></noscript>
    <script>(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start': new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0], j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src= '//www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f); })(window,document,'script','dataLayer','GTM-58RLH5');</script>
    <!-- End Google Tag Manager -->

    <!-- Global site tag (gtag.js) - Google Analytics -->
    <script async src="https://www.googletagmanager.com/gtag/js?id=UA-12395217-16"></script>
    <script>
      window.dataLayer = window.dataLayer || [];
      function gtag(){dataLayer.push(arguments);}
      gtag('js', new Date());
      gtag('config', 'UA-12395217-16');
    </script>

    <!--BEGIN QUALTRICS WEBSITE FEEDBACK SNIPPET-->
    <script type="text/javascript">
      (function(){var g=function(e,h,f,g){
      this.get=function(a){for(var a=a+"=",c=document.cookie.split(";"),b=0,e=c.length;b<e;b++){for(var d=c[b];" "==d.charAt(0);)d=d.substring(1,d.length);if(0==d.indexOf(a))return d.substring(a.length,d.length)}return null};
      this.set=function(a,c){var b="",b=new Date;b.setTime(b.getTime()+6048E5);b="; expires="+b.toGMTString();document.cookie=a+"="+c+b+"; path=/; "};
      this.check=function(){var a=this.get(f);if(a)a=a.split(":");else if(100!=e)"v"==h&&(e=Math.random()>=e/100?0:100),a=[h,e,0],this.set(f,a.join(":"));else return!0;var c=a[1];if(100==c)return!0;switch(a[0]){case "v":return!1;case "r":return c=a[2]%Math.floor(100/c),a[2]++,this.set(f,a.join(":")),!c}return!0};
      this.go=function(){if(this.check()){var a=document.createElement("script");a.type="text/javascript";a.src=g;document.body&&document.body.appendChild(a)}};
      this.start=function(){var a=this;window.addEventListener?window.addEventListener("load",function(){a.go()},!1):window.attachEvent&&window.attachEvent("onload",function(){a.go()})}};
      try{(new g(100,"r","QSI_S_ZN_emkP0oSe9Qrn7kF","https://znemkp0ose9qrn7kf-elastic.siteintercept.qualtrics.com/WRSiteInterceptEngine/?Q_ZID=ZN_emkP0oSe9Qrn7kF")).start()}catch(i){}})();
    </script><div id="ZN_emkP0oSe9Qrn7kF"><!--DO NOT REMOVE-CONTENTS PLACED HERE--></div>
    <!--END WEBSITE FEEDBACK SNIPPET-->

    <div id="elastic-nav" style="display:none;"></div>
    <script src="https://www.elastic.co/elastic-nav.js"></script>

    <!-- Subnav -->
    <div>
      <div>
        <div class="tertiary-nav d-none d-md-block">
          <div class="container">
            <div class="p-t-b-15 d-flex justify-content-between nav-container">
              <div class="breadcrum-wrapper"><span><a href="/guide/" style="font-size: 14px; font-weight: 600; color: #000;">Docs</a></span></div>
            </div>
          </div>
        </div>
      </div>
    </div>

    <div class="main-container">
      <section id="content">
        <div class="content-wrapper">

          <section id="guide" lang="en">
            <div class="container">
              <div class="row">
                <div class="col-xs-12 col-sm-8 col-md-8 guide-section">
                  <!-- start body -->
                  <div class="page_header">
<p>
  <strong>WARNING</strong>: The 2.x versions of Elasticsearch have passed their
  <a href="https://www.elastic.co/support/eol">EOL dates</a>. If you are running
  a 2.x version, we strongly advise you to upgrade.
</p>
<p>
  This documentation is no longer maintained and may be removed. For the latest
  information, see the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/index.html">current
  Elasticsearch documentation</a>.
</p>
</div>
<div id="content">
<div class="breadcrumbs">
<span class="breadcrumb-link"><a href="index.html">Elasticsearch: The Definitive Guide [2.x]</a></span>
»
<span class="breadcrumb-link"><a href="aggregations.html">Aggregations</a></span>
»
<span class="breadcrumb-link"><a href="docvalues-and-fielddata.html">Doc Values and Fielddata</a></span>
»
<span class="breadcrumb-node">Preventing Combinatorial Explosions</span>
</div>
<div class="navheader">
<span class="prev">
<a href="preload-fielddata.html">« Preloading Fielddata</a>
</span>
<span class="next">
<a href="_closing_thoughts.html">Closing Thoughts »</a>
</span>
</div>
<div class="section">
<div class="titlepage"><div><div>
<h2 class="title">
<a id="_preventing_combinatorial_explosions"></a>Preventing Combinatorial Explosions<a class="edit_me edit_me_private" rel="nofollow" title="Editing on GitHub is available to Elastic" href="https://github.com/elastic/elasticsearch-definitive-guide/edit/2.x/300_Aggregations/120_breadth_vs_depth.asciidoc">edit</a>
</h2>
</div></div></div>
<p>The <code class="literal">terms</code> bucket dynamically builds buckets based on your data; it doesn’t
know up front how many buckets will be generated.  While this is fine with a
single aggregation, think about what can happen when one aggregation contains
another aggregation, which contains another aggregation, and so forth. The combination of
unique values in each of these aggregations can lead to an explosion in the
number of buckets generated.</p>
<p>Imagine we have a modest dataset that represents movies.  Each document lists
the actors in that movie:</p>
<div class="pre_wrapper lang-js">
<pre class="programlisting prettyprint lang-js">{
  "actors" : [
    "Fred Jones",
    "Mary Jane",
    "Elizabeth Worthing"
  ]
}</pre>
</div>
<p>If we want to determine the top 10 actors and their top costars, that’s trivial
with an aggregation:</p>
<div class="pre_wrapper lang-js">
<pre class="programlisting prettyprint lang-js">{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" : "actors",
         "size" :  10
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}</pre>
</div>
<p>This will return a list of the top 10 actors, and for each actor, a list of their
top five costars.  This seems like a very modest aggregation; only 50
values will be returned!</p>
<p>However, this seemingly innocuous query can easily consume a vast amount of
memory. You can visualize a <code class="literal">terms</code> aggregation as building a tree in memory.
The <code class="literal">actors</code> aggregation will build the first level of the tree, with a bucket
for every actor.  Then, nested under each node in the first level, the
<code class="literal">costars</code> aggregation will build a second level, with a bucket for every costar, as seen in <a class="xref" href="_preventing_combinatorial_explosions.html#depth-first-1" title="Build full depth tree">Figure 42, “Build full depth tree”</a>. That means that a single movie will generate n<sup>2</sup> buckets!</p>
<div id="depth-first-1" class="imageblock">
<div class="content">
<img src="images/300_120_depth_first_1.svg" alt="Build full depth tree">
</div>
<div class="title">Figure 42. Build full depth tree</div>
</div>
<p>To use some real numbers, imagine each movie has 10 actors on average. Each movie
will then generate 10<sup>2</sup> == 100 buckets.  If you have 20,000 movies, that’s
roughly 2,000,000 generated buckets.</p>
<p>Now, remember, our aggregation is simply asking for the top 10 actors and their
co-stars, totaling 50 values.  To get the final results, we have to generate
that tree of 2,000,000 buckets, sort it, and finally prune it such that only the
top 10 actors are left. This is illustrated in <a class="xref" href="_preventing_combinatorial_explosions.html#depth-first-2" title="Sort tree">Figure 43, “Sort tree”</a> and <a class="xref" href="_preventing_combinatorial_explosions.html#depth-first-3" title="Prune tree">Figure 44, “Prune tree”</a>.</p>
<div id="depth-first-2" class="imageblock">
<div class="content">
<img src="images/300_120_depth_first_2.svg" alt="Sort tree">
</div>
<div class="title">Figure 43. Sort tree</div>
</div>
<div id="depth-first-3" class="imageblock">
<div class="content">
<img src="images/300_120_depth_first_3.svg" alt="Prune tree">
</div>
<div class="title">Figure 44. Prune tree</div>
</div>
<p>At this point you should be quite distraught.  Twenty thousand documents is paltry,
and the aggregation is pretty tame.  What if you had 200 million documents, wanted
the top 100 actors and their top 20 costars, as well as the costars' costars?</p>
<p>You can appreciate how quickly combinatorial expansion can grow, making this
strategy untenable.  There is not enough memory in the world to support uncontrolled
combinatorial explosions.</p>
<div class="section">
<div class="titlepage"><div><div>
<h3 class="title">
<a id="_depth_first_versus_breadth_first"></a>Depth-First Versus Breadth-First<a class="edit_me edit_me_private" rel="nofollow" title="Editing on GitHub is available to Elastic" href="https://github.com/elastic/elasticsearch-definitive-guide/edit/2.x/300_Aggregations/120_breadth_vs_depth.asciidoc">edit</a>
</h3>
</div></div></div>
<p>Elasticsearch allows you to change the <em>collection mode</em> of an aggregation, for
exactly this situation.  The strategy we outlined previously—​building the tree fully
and then pruning—​is called <em>depth-first</em> and it is the default.  Depth-first
works well for the majority of aggregations, but can fall apart in situations
like our actors and costars example.</p>
<p>For these special cases, you should use an alternative collection strategy called
<em>breadth-first</em>.  This strategy works a little differently.  It executes the first
layer of aggregations, and <em>then</em> performs a pruning phase before continuing, as illustrated in <a class="xref" href="_preventing_combinatorial_explosions.html#breadth-first-1" title="Build first level">Figure 45, “Build first level”</a> through <a class="xref" href="_preventing_combinatorial_explosions.html#breadth-first-3" title="Prune first level">Figure 47, “Prune first level”</a>.</p>
<p>In our example, the <code class="literal">actors</code> aggregation would be executed first.  At this
point, we have a single layer in the tree, but we already know who the top 10
actors are! There is no need to keep the other actors since they won’t be in
the top 10 anyway.</p>
<div id="breadth-first-1" class="imageblock">
<div class="content">
<img src="images/300_120_breadth_first_1.svg" alt="Build first level">
</div>
<div class="title">Figure 45. Build first level</div>
</div>
<div id="breadth-first-2" class="imageblock">
<div class="content">
<img src="images/300_120_breadth_first_2.svg" alt="Sort first level">
</div>
<div class="title">Figure 46. Sort first level</div>
</div>
<div id="breadth-first-3" class="imageblock">
<div class="content">
<img src="images/300_120_breadth_first_3.svg" alt="Prune first level">
</div>
<div class="title">Figure 47. Prune first level</div>
</div>
<p>Since we already know the top ten actors, we can safely prune away the rest of the
long tail. After pruning, the next layer is populated based on <em>its</em> execution mode,
and the process repeats until the aggregation is done, as illustrated in <a class="xref" href="_preventing_combinatorial_explosions.html#breadth-first-4" title="Populate full depth for remaining nodes">Figure 48, “Populate full depth for remaining nodes”</a>. This prevents the
combinatorial explosion of buckets and drastically reduces memory requirements
for classes of queries that are amenable to breadth-first.</p>
<div id="breadth-first-4" class="imageblock">
<div class="content">
<img src="images/300_120_breadth_first_4.svg" alt="Step 4: populate full depth for remaining nodes">
</div>
<div class="title">Figure 48. Populate full depth for remaining nodes</div>
</div>
<p>To use breadth-first, simply enable it via the <code class="literal">collect</code> parameter:</p>
<div class="pre_wrapper lang-js">
<pre class="programlisting prettyprint lang-js">{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" :        "actors",
         "size" :         10,
         "collect_mode" : "breadth_first" <a id="CO226-1"></a><i class="conum" data-value="1"></i>
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}</pre>
</div>
<div class="calloutlist">
<table border="0" summary="Callout list">
<tr>
<td align="left" valign="top" width="5%">
<p><a href="#CO226-1"><i class="conum" data-value="1"></i></a></p>
</td>
<td align="left" valign="top">
<p>Enable <code class="literal">breadth_first</code> on a per-aggregation basis.</p>
</td>
</tr>
</table>
</div>
<p>Breadth-first should be used only when you expect more buckets to be generated
than documents landing in the buckets.  Breadth-first works by caching
document data at the bucket level, and then replaying those documents to child
aggregations after the pruning phase.</p>
<p>The memory requirement of a breadth-first aggregation is linear to the number
of documents in each bucket prior to pruning.  For many aggregations, the
number of documents in each bucket is very large.  Think of a histogram with
monthly intervals: you might have thousands or hundreds of thousands of
documents per bucket.  This makes breadth-first a bad choice, and is why
depth-first is the default.</p>
<p>But for the actor example—​which generates a large number of
buckets, but each bucket has relatively few documents—​breadth-first is much
more memory efficient, and allows you to build aggregations that would
otherwise fail.</p>
</div>

</div>
<div class="navfooter">
<span class="prev">
<a href="preload-fielddata.html">« Preloading Fielddata</a>
</span>
<span class="next">
<a href="_closing_thoughts.html">Closing Thoughts »</a>
</span>
</div>
</div>

                  <!-- end body -->
                </div>
                <div class="col-xs-12 col-sm-4 col-md-4" id="right_col">
                  <div id="rtpcontainer" style="display: block;">
                    <div class="mktg-promo">
                      <h3>Most Popular</h3>
                      <ul class="icons">
                        <li class="icon-elasticsearch-white"><a href="https://www.elastic.co/webinars/getting-started-elasticsearch?baymax=default&amp;elektra=docs&amp;storm=top-video">Get Started with Elasticsearch: Video</a></li>
                        <li class="icon-kibana-white"><a href="https://www.elastic.co/webinars/getting-started-kibana?baymax=default&amp;elektra=docs&amp;storm=top-video">Intro to Kibana: Video</a></li>
                        <li class="icon-logstash-white"><a href="https://www.elastic.co/webinars/introduction-elk-stack?baymax=default&amp;elektra=docs&amp;storm=top-video">ELK for Logs &amp; Metrics: Video</a></li>
                      </ul>
                    </div>
                  </div>
                </div>
              </div>
            </div>
          </section>

        </div>


<div id="elastic-footer"></div>
<script src="https://www.elastic.co/elastic-footer.js"></script>
<!-- Footer Section end-->

      </section>
    </div>

<script src="/guide/static/jquery.js"></script>
<script type="text/javascript" src="/guide/static/docs.js"></script>
<script type="text/javascript">
  window.initial_state = {}</script>
  </body>
</html>
